package graph;

import java.util.*;

public class TheTimeWhenTheNetworkBecomesIdle2039 {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int[] distance = new int[patience.length];

        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            Set<Integer> set = graph.getOrDefault(edges[i][0], new HashSet<>());
            set.add(edges[i][1]);
            graph.put(edges[i][0], set);
            Set<Integer> set2 = graph.getOrDefault(edges[i][1], new HashSet<>());
            set2.add(edges[i][0]);
            graph.put(edges[i][1], set2);
        }

        bfs(graph, distance);
        int max = 0;
        for (int i = 0; i < patience.length; i++) {
            max = Math.max(max,patience[i]>=2*distance[i]?2*distance[i]+1:patience[i] * ((2 * distance[i] - 1) / patience[i]) + 2 * distance[i] + 1);
        }
        return max;
    }

    private void bfs(Map<Integer, Set<Integer>> graph, int[] distance) {
        LinkedList<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.push(0);
        int dis = 0;
        while (queue.size()!=0){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer node = queue.pop();
                if(!visited.contains(node)){
                  visited.add(node);
                  distance[node] = dis;
                  queue.addAll(graph.get(node));
                }
            }
            dis++;
        }
    }
}
